package com.dyz.LeetCodeforSwordFingerOffer;



import java.util.ArrayList;
import java.util.HashSet;

/**
 * @author: daiyizheng
 * @date: 2021/7/6 22:49
 * @description:
 */
public class Permutation38 {
    public String[] permutation(String s) {
        if(s==null||s.length()==0){
            return new String[]{};
        }
        char [] a = s.toCharArray();
        ArrayList<String> ans = new ArrayList<>();
        dfs(a, ans, 0, s.length());
        //去重
        ans = new ArrayList<>(new HashSet<>(ans));
        String [] string = new String[ans.size()];
        int size =0;
        for(String val:ans){
            string[size++]=val;
        }
        return string;
    }
    private void dfs(char[] a, ArrayList<String> ans, int index, int length){
        if(index==length-1){
            String res = change(a);
            ans.add(res);
        }else{
            for (int i=index;i<length;i++){
                //交换顺序
                char temp = a[i];
                a[i] = a[index];
                a[index] = temp;
                //递归
                dfs(a, ans, index+1, length);
                //回溯还原
                temp = a[i];
                a[i] = a[index];
                a[index] = temp;
            }
        }
    }
    private String change(char[] a){
        StringBuilder stringBuilder = new StringBuilder();
        for (char val: a) {
            stringBuilder.append(val);
        }
        return stringBuilder.toString();
    }
}
